package com.leetcode.程序员面试金典.medium;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * @author 覃国强
 * @date 2021-04-14 12:29
 */
public class 面试题_17_15_最长单词 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    String[] words = {"cat", "banana", "dog", "nana", "walk", "walker", "dogwalker", "dogwalkert"};
    String result = solution.longestWord(words);
    System.out.println(result);
  }


  static
  class Solution {

    public String longestWord(String[] words) {
      quickSort(words);
      Set<String> set = new HashSet<>(Arrays.asList(words));
      for (String word : words) {
        set.remove(word);
        if (isMatch(word, set)) {
          return word;
        }
      }
      return "";
    }

    private boolean isMatch(String word, Set<String> set) {
      if (word.length() == 0) {
        return true;
      }
      if (set.contains(word)) {
        return true;
      }
      for (String key : set) {
        if (word.startsWith(key)) {
          boolean match = isMatch(word.substring(key.length()), set);
          if (match) {
            return true;
          }
        }
      }
      return false;
    }

    public void quickSort(String[] words) {
      quickSort(words, 0, words.length - 1);
    }

    public void quickSort(String[] words, int left, int right) {
      if (left >= right || left < 0 || left >= words.length || right < 0 || right >= words.length) {
        return;
      }

      String pivot = words[left];
      int i = left;
      int j = right;
      while (i < j) {
        // 从右往左找第一个小于等于 pivot 的位置，判断要大于
        while (i < j && compare(words[j], pivot) > 0) {
          --j;
        }
        // 从左往右找第一个大于等于 pivot 的位置，判断要小于
        while (i < j && compare(words[i], pivot) < 0) {
          ++i;
        }
        if (i < j && words[i].equals(words[j])) {
          ++i;
        } else {
          swap(i, j, words);
        }
      }
      quickSort(words, left, i - 1);
      quickSort(words, j + 1, right);
    }

    private void swap(int i, int j, String[] words) {
      String tmp = words[i];
      words[i] = words[j];
      words[j] = tmp;
    }

    /**
     * str1 < str2
     *
     * @param str1
     * @param str2
     * @return
     */
    public int compare(String str1, String str2) {
      int diffLength = str1.length() - str2.length();
      if (diffLength == 0) {
        return str1.compareTo(str2);
      }
      return diffLength > 0 ? -1 : 1;
    }
  }

}
